作業系統L7－死結

死結特性

• 互斥:一次一個行程占用資源
• 占用與等候:至少一個行程佔用資源且正等待其他資源
• 不可搶先:一個資源完成工作後才會被釋放
• 循環式等候:一組形成被循環占用

資源配置圖

• 要求邊
• 分配邊
• 
• 

處理死結

預防死結

• 互斥(Mutual Exclusion) :可共用資源可打破互斥，但不可共用資源無法，天生較難預防
• 佔用與等候(Hold and Wait):一個行程要求其他資源時不得佔有資源
  • 資源長時間被分配又長時間不用，使用率低
  • 可能無限期等待，飢餓
• 不可搶先(No Preemption):程序申請資源必須等待時，強制取消原資源的程序給新程序
  • 只試用容易取消與方便保存資訊的資源，EX:cpu暫存
• 循環式等候(Circular Wait): 強迫要求j>i的線性順序要求
• 缺點:裝置使用率低 生產量低

避免死結

    定義資源配置狀態(資源數量 最大要求量)，並利用死結演算法確保安全狀態

銀行家演算法

• Available:可用的例證數
• Max:行程最多可要求的例證量
• Allocation:行程已佔用的數量
• Need:行程還需要的例證

1. 當要求量小於需求，跳到步驟2，無法給與要求量
2. 當要求量小於可用量，跳到步驟3 無法取得資源
3. 修改配置數量
4. 執行安全演算法驗證，如果是回傳安全狀態就分配資源，不行就回原狀態

Available= Available –Request;//可用量被要求後剩下的量
Allocationi= Allocationi+ Requesti;//占用量增加運行的要求
Needi=Needi–Requesti//要求量完成後剩下的需求量

安全演算法

1. 定義初始值

Work = Available
Finish [i] =false 
//對i= 0, 1, ..., n-1

2. (需求不足可用資源 || 行程都完成時)，跳出迴圈到步驟4

(a) Finish[i] = false
(b) Needi<=Work

3. 在迴圈中持續執行程序

Work= Work + Allocationi
Finish[i] =true
//回到步驟2

4. 若所有行程都完成，則為安全狀態

偵測死結

偵測圖型是否循環

偵測演算法

• 跟安全演算法相似，m*(n^2)
• 

資源有多個裝置

• 優點:執行頻率太高，浪費時間
• 缺點:可知道死結處

資源有一個裝置

• 優點:頻率低
• 缺點:不知死結處

恢復死結

• 程序中止

  • 中止所有程序:時間費用高，先前結果要重新計算
  • 一次中止一個程序:每次中止一個要執行死結演算法判斷

• 資源搶奪

    搶奪三因素
  

  • 選擇犧牲者(Victim):盡可能減少成本
  • 撤回(Rollback):被剝奪者回到安全狀態
  • 飢餓(Starvation):保證被犧牲者搶奪次數